package com.yww.leetcode.hashtable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author yww
 * @description 49. 字母异位词分组
 * @since 2024/2/22 11:12
 */
public class GroupAnagrams49 {
    // 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
    // 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
    public List<List<String>> groupAnagrams(String[] strs) {
        return groupAnagrams2(strs);
    }

    /*
          解法1 思路
          1. 遍历字符串数组，每个字符串中的字符重新排序后作为 key
          2. 所谓分组，其实就是准备一个集合，把这些单词加入到 key 相同的集合中
          3. 返回分组结果
       */
    public List<List<String>> groupAnagrams1(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortStr = new String(chars);
            List<String> list = map.computeIfAbsent(sortStr, k -> new ArrayList<>());
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        // 局部类
        class Key {
            final int[] arr = new int[26];

            Key(String str) {
                for (char c : str.toCharArray()) {
                    arr[c - 'a']++;
                }
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Key key = (Key) o;
                return Arrays.equals(arr, key.arr);
            }

            @Override
            public int hashCode() {
                return Arrays.hashCode(arr);
            }
        }
        HashMap<Key, List<String>> map = new HashMap<>();
        for (String str : strs) {
            Key key = new Key(str);
            List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(str);

        }
        return new ArrayList<>(map.values());
    }

}
